package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/7/12.<br><br>
 *
 * 计数质数
 */
public class Topic204 {
    public static void main(String[] args) {
        Topic204 instance = new Topic204();

        System.out.println(instance.countPrimes(0));
        System.out.println(instance.countPrimes(1));
        System.out.println(instance.countPrimes(10));
        System.out.println(instance.countPrimes(1500000));
    }

    public int countPrimes(int n) {
        if(n < 2) {
            return 0;
        }

        int counter = 0;
        boolean[] notPrimes = new boolean[n];
        for(int i = 2; i < n; i++) {
            if(!notPrimes[i]) {
                counter++;
            }

            for(int j = 2; j * i < n; j++) {
                notPrimes[j * i] = true;
            }
        }

        return counter;
    }
}
